/*
 *
 *  File: 'graph.h'
 *
 *  Author: Samip Shah <samipshah@alumni.cmu.edu>
 *  Date: Sep 08, 2011
 *
 */

#ifndef INCLUDED_GRAPH_H
#define INCLUDED_GRAPH_H

#include <vector>
#include <stdio.h>
#include <iostream>

#define DATA(x) (x)->data
#define ADJNODE(x, y) ((x)->adjnodes)[y]

template<typename T>
class Graph 
{

	typedef void (*visit_func)(T& a, T& b);
	struct Node {
		T data;
		std::vector<Node*> adjnodes;
	};

	struct NodeHolder {
		Node* node;
		bool visited;
	};

	std::vector<Node*> nodePool;
	Node* findNodeInternal(T& data) ;

	public:

	enum CONNECTION {
		ONE_WAY,
		BOTH_WAY
	};

	bool addNode(T data);
	bool createConnection(T a, T b, CONNECTION type);
	void printAllConnections(visit_func f = NULL);
	bool pathExists(T* arr, int len);

  // add clear all method to delete all the nodes and connections
};

template<typename T>
bool Graph<T>::pathExists(T* arr, int len) {
	if(len <= 0)
		return false;

	Node* tnode = findNodeInternal(arr[0]);
	if(tnode == NULL) {
		return false;
	}
	for (int i = 1; i < len ; i++) {
		int size = tnode->adjnodes.size();
		int j=0;
		for(; j < size; j++) {
			if(arr[i] == DATA(ADJNODE(tnode, j))) {
				tnode=ADJNODE(tnode,j);
				break;
			}
		}
		if(j == size)
			return false;
	}
	
	return true;
}

template<typename T>
void Graph<T>::printAllConnections(visit_func f) {
	int size = nodePool.size();
	for(int i = 0; i < size; i++)
	{
		int isize = nodePool[i]->adjnodes.size();
		for(int j = 0; j < isize; j++)
		{
			if(f == NULL) {
				std::cout << DATA(nodePool[i]) << " - " 
				<< DATA(ADJNODE(nodePool[i], j)) 
				<< std::endl;
			}
			else {
				f(DATA(nodePool[i]), 
					DATA(ADJNODE(nodePool[i],j)));
			}
		}
		std::cout << std::endl;
	}
}

template<typename T>
typename Graph<T>::Node* Graph<T>::findNodeInternal(T& data) {
	int size = nodePool.size();
	for(int i=0; i < size; i++)
	{
		if(DATA(nodePool[i]) == data) 
			return nodePool[i];
	}

	return NULL;
}

template<typename T>
bool Graph<T>::createConnection(T a, T b, CONNECTION type) {
	switch(type) {
		case ONE_WAY:
			{
				Node* aptr = findNodeInternal(a);
				Node* bptr = findNodeInternal(b);
				if(!aptr || !bptr)
					return false;
				
				aptr->adjnodes.push_back(bptr);
			} break;
		case BOTH_WAY:
			{
				Node* aptr = findNodeInternal(a);
				Node* bptr = findNodeInternal(b);
				if(!aptr || !bptr)
					return false;
				
				aptr->adjnodes.push_back(bptr);
				bptr->adjnodes.push_back(aptr);
			} break;
		default:
			{
				fprintf(stderr, \
					"Invalid Connection\n");
				return false;
			}
	}

	return true;
}

template<typename T>
bool Graph<T>::addNode(T data) {
	Node* newNode = new Node();
	DATA(newNode) = data;

	if(findNodeInternal(data)) {
		fprintf(stderr, "Duplicate Entry\n");
		return false;
	}

	nodePool.push_back(newNode);
	return true;
}

#undef DATA
#undef ADJNODE

#endif
